Dane jest n liczb całkowitych dodatnich po jednej w każdym wierszu. Każda liczba jest z zakresu od 1 do 100 000. Napisz program, który zliczy liczby, które są potęgami liczby 3 (czyli liczbami postaci 1 = 3⁰, 3 = 3¹, 9 = 3² itd.).

Wejście

W pierwszym wierszu zapisano liczbę n z przedziału od 2 do 500. W kolejnych n wierszach znajdują się liczby całkowite z przedziału od 1 do 100 000.

Wyjście

Jedna liczba, informująca ile liczb spełnia warunki zadania.

Przykład

            3
		3
		49
		9
          

            2
          

Skopiuj wejście